import java.util.List;

/**
 * Created by L.jp
 * Description:在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例
 * 如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 * User: 86189
 * Date: 2021-12-24
 * Time: 21:16
 */
//这个题目是删除链表中所有重复的节点
 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null){
            return pHead;
        }
        //考虑到有可能链表节点的值都相等，如果不借助虚拟节点的话，就把prev定义在pHead、last定义在prev,next的话,那么就需要删除所有节点，然而返回值不好确定
        //所以借助一个虚拟节点，让prev在虚拟节点这，last就在pHead这，这样就可以避免全都一样的情况，可以直接删除，返回newHead.next
        //借助一个新的表头，更好操作,其实头结点只是一个虚拟的节点，一个标识而已，没有具体意义
        ListNode newHead=new ListNode(0);
        //将新的头结点拼接，
        newHead.next=pHead;
        //对于这个题目而言，prev和last一开始就必须相差一个节点，不能在同一个节点，否则没有办法删除重复的节点，可以自己画图试试
        //定义前节点用于找到最后一个不重复的节点，也就是开始重复节点的前一个
        ListNode prev=newHead;
        //定义后节点用于遍历重复的节点
        ListNode last=prev.next;
        while(last!=null){
            //找到重复开始的前一个节点
            while (last.next!=null && last.val!=last.next.val){
                prev=prev.next;
                last=last.next;
            }
            //找到重复的最后一个节点
            while(last.next!=null && last.val==last.next.val){
                last=last.next;
            }
            //在寻找重复节点的同时，也同时判断这个条件，说明找到了重复的一段区间，需要删除节点.在找重复节点的时候，prev节点一直是停留在重复节点的前一个位置
            if(prev.next!=last){
                prev.next=last.next;//这里包含了两种情况，一个是最后一个重复节点的后面还有一些节点，第二个是最后一个节点作为尾结点，这个代码都适用
            }
            //走到这里说明删除了一些重复的节点，然后又需要再找重复的节点，prev和last需要恢复和刚开始查找的时候一样的位置，因为删除重复节点之后last还停留在最后一个重复的节点，需要跳出来
            last=last.next;

        }
        //newHead是我们构造的虚拟节点，而不是题目要求返回的节点，所以要返回虚拟头结点的下一个节点
        return newHead.next;
    }
}
